4853. Кратчайший путь
Задан неориентированный граф.
Найдите кратчайший путь от вершины a до вершины b.
Вход. В первой строке находится два целых числа n и m
(1 ≤ n ≤ 5 * 104,
1 ≤ m ≤ 105) –
количества вершин и рёбер соответственно. Во второй строке заданы целые числа a и b
– стартовая и конечная вершина соответственно. Далее идут m строк, описывающие рёбра.
Выход. Если пути между
a и b нет, то выведите -1. Иначе выведите в первой строке длину l кратчайшего пути между этими двумя
вершинами в рёбрах, а во второй строке выведите l + 1 число – вершины этого пути.
|
Пример
входа |
Пример
выхода |
|
4 5 1 4 1 3 3 2 2 4 2 1 2 3 |
2 1 2 4 |
РЕШЕНИЕ
графы –
поиск в ширину
Анализ алгоритма
В задаче
необходимо реализовать поиск в ширину, построив массив кратчайших расстояний
dist и массив предков parent от истока до всех вершин. Поскольку количество
вершин порядка 50000, то граф следует хранить в виде списка смежности.
Пример
Приведенный в
примере граф имеет вид:
Реализация алгоритма
Объявим список
смежности g для хранения графа, а также дополнительные массивы: dist[i] хранит кратчайшее расстояние от
истока до вершины i, parent[i] хранит предка вершины i при поиске в ширину.
#define MAX 50010
int used[MAX], dist[MAX], parent[MAX];
vector<vector<int> > g;
Функция bfs реализует поиск
в ширину из вершины start. Очередь реализуем в виде локального массива q размера
MAX (в любой момент времени количество вершин в очереди будет не больше чем
количество вершин в графе). Head и Tail – указатели на голову и конец
очереди.
void bfs(int
start)
{
memset(used,0,sizeof(used));
memset(parent,-1,sizeof(parent));
memset(dist,-1,sizeof(dist));
dist[start] = 0;
int q[MAX],
Head = 0, Tail = 1;
q[Head] = start; used[start] = 1;
while(Head
< Tail)
{
int v =
q[Head++];
Если из v имеется ребро в to, и
при этом вершина to еще не пройдена,
то идем в нее (ребро (v, to) является ребром дерева при поиске в
ширину).
for(int i = 0; i < g[v].size(); i++)
{
int to =
g[v][i];
if
(!used[to])
{
q[Tail++] = to;
used[to] = 1;
dist[to] = dist[v] + 1;
parent[to] = v;
}
}
}
}
Используя массив
предков parent, выводим кратчайший путь от истока до вершины v. Перед каждой вершиной, кроме начальной, выводим пробел. Вершина v является начальной, если parent[v] = -1.
void path(int
v)
{
if (v == -1) return;
path(parent[v]);
if (parent[v]
!= -1) printf(" ");
printf("%d",v);
}
Основная часть
программы. Читаем входные данные.
scanf("%d %d",&n,&m);
scanf("%d %d",&a,&b);
g.resize(n+1);
while(scanf("%d
%d",&u,&v) == 2)
{
g[u].push_back(v);
g[v].push_back(u);
}
Запускаем поиск в ширину из вершины x.
bfs(a);
Если вершина b при поиске не достигнута (parent[b] равно -1), то выводим -1. Иначе выводим величину кратчайшего
расстояния до b и соответствующий
кратчайший путь.
if (parent[b] == -1)
printf("-1\n");
else
{
printf("%d\n",dist[b]);
path(b);
printf("\n");
}
Реализация алгоритма – STL
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int i, j, n, m, a, b, u,
v;
vector<int> dist, parent;
vector<vector<int> > g;
void bfs(int start)
{
parent = vector<int>(n + 1, -1);
dist = vector<int>(n + 1, -1);
dist[start] = 0;
queue<int> q;
q.push(start);
while (!q.empty())
{
int v = q.front(); q.pop();
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (dist[to] == -1)
{
q.push(to);
dist[to] = dist[v] + 1;
parent[to] = v;
}
}
}
}
int main(void)
{
scanf("%d %d", &n,
&m);
scanf("%d %d", &a,
&b);
g.resize(n
+ 1);
while (scanf("%d %d", &u, &v) == 2)
{
g[u].push_back(v);
g[v].push_back(u);
}
bfs(a);
if (parent[b] == -1)
printf("-1\n");
else
{
printf("%d\n", dist[b]);
vector<int> path(1, b);
while (parent[b] != -1)
{
b =
parent[b];
path.push_back(b);
}
for (i = path.size() - 1; i >= 0; i--)
printf("%d ", path[i]);
printf("\n");
}
return 0;
}
Java реализация
import java.util.*;
public class Main
{
static ArrayList<Integer>[] g;
static int dist[], parent[];
static int n, m;
static void bfs(int start)
{
Arrays.fill(dist,-1);
dist[start] = 0;
Arrays.fill(parent,-1);
Queue<Integer> q = new LinkedList<Integer>();
q.add(start);
while(!q.isEmpty())
{
int v = q.poll();
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v].get(i);
if (dist[to] == -1)
{
q.add(to);
dist[to] = dist[v] + 1;
parent[to] = v;
}
}
}
}
@SuppressWarnings("unchecked")
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
n = con.nextInt(); m = con.nextInt();
int a = con.nextInt();
int b = con.nextInt();
g = new ArrayList[n+1];
for(int i = 0; i <= n; i++)
g[i] = new ArrayList<Integer>();
dist = new int[n+1];
parent = new int[n+1];
for (int i = 0; i < m; i++)
{
int u = con.nextInt();
int v = con.nextInt();
g[u].add(v);
g[v].add(u);
}
bfs(a);
if (parent[b] == -1)
System.out.println("-1");
else
{
System.out.println(dist[b]);
Vector<Integer> path = new
Vector<Integer>();
path.add(b);
while (parent[b] != -1)
{
b = parent[b];
path.add(b);
}
for (int i = path.size() - 1; i >= 0; i--)
System.out.print(path.get(i) + " ");
System.out.println();
}
con.close();
}
}